操作系统 - 进程与CPU调度

2026年9月20日笔记学习 / 操作系统 zh-CN

本篇是操作系统课程笔记的第一篇，对应《操作系统导论》中进程、进程 API、受限直接执行与 CPU 调度等主题。这里的“第一篇”是笔记编排，不是教材章号。

阅读时先抓住一条线：程序怎样成为进程 → 进程何时运行或等待 → 如何创建另一个进程 → 多个进程怎样分享 CPU。 以下以单线程进程为主要模型，Unix 风格接口用于说明创建与执行。

⭐ 本章考试重点：进程的步骤、进程状态的转换、fork() 函数的具体过程。对应下文 §1.1、§1.2 和 §2.1—2.3。

一、程序与进程

程序是静态的指令与数据；进程（process） 是程序的一次运行实例。可以简明类比：程序如静态菜谱，进程是依谱烹饪的动态执行过程；同一份菜谱可同时对应多个互不干扰的独立进程。

操作系统需要记录进程的地址空间信息、寄存器状态、打开文件、标识符及调度状态等。教材常以进程控制块（PCB）概括这类元数据；实际内核的数据结构和拆分方式各异。

1.1 从程序到进程：创建与执行的步骤 ⭐

⭐ 考试考点：进程的步骤。 先掌握程序如何被准备为一个可执行的进程，再与后面的 fork() 创建路径区分。

从操作系统的职责看，启动一个新程序需要完成以下工作；这是教学上的逻辑顺序，不要求所有内核逐项按此顺序实现。

建立管理信息：分配进程标识（PID）及内核数据结构（PCB），记录父子关系、安全凭证与调度优先级。
建立地址空间：为程序代码段、全局静态数据段等建立虚拟内存映射。装载并不要求立刻把整个可执行文件全部读入物理内存，实际支持按需调页（Demand Paging）。
准备运行环境：设置用户栈（放置参数 argv 和环境变量 envp），准备动态堆分配所需的起始空间，并关联标准输入输出等文件引用。
设置初始执行上下文：初始化程序计数器（PC，通常先指向语言运行时启动入口，再调用 main()）、栈指针（SP）等寄存器，使其具备执行条件。
进入就绪并等待调度：准备完成不等于立即运行；调度器选中后，CPU 才真正开始执行该进程。

记忆线索：建记录 → 建空间 → 备环境 → 设上下文 → 等调度。

在 Unix 的 fork()＋exec() 路径中，这些职责分布在不同操作中：fork() 创建子进程并继承已有环境，exec() 将调用进程的程序映像替换为新程序。不要把上面的概念步骤误记为“fork() 每次都从磁盘重新装入程序”。

1.2 三种基本状态与转换 ⭐

⭐ 考试考点：进程状态的转换。 重点关注各状态之间的转换条件与不可逾越的边界。

stateDiagram-v2
    就绪 --> 运行: 被调度器选中（分配CPU）
    运行 --> 就绪: 时间片耗尽 / 被更高优先级抢占
    运行 --> 阻塞: 发起I/O等待 / 等待互斥锁或事件
    阻塞 --> 就绪: I/O完成 / 等待的事件满足

就绪（ready）：具备执行条件，正在等待 CPU。
运行（running）：正在 CPU 上执行指令。
阻塞（blocked）：因等待 I/O 或同步事件而挂起，即使分配 CPU 也无法推进。

转换	触发条件	说明与易错点
就绪 → 运行	调度器选中该任务，完成上下文恢复	就绪队列中的任务都具备运行能力，仅在等待 CPU
运行 → 就绪	时间片耗尽、被高优先级任务抢占，或主动让出（yield）	任务本身仍可运行，只是暂时交出 CPU
运行 → 阻塞	发起需要等待的 I/O，或等待尚未满足的事件	等待期间不应占用 CPU 空转
阻塞 → 就绪	I/O 完成或等待的事件满足	仅代表重新具备运行资格，仍需调度器分配 CPU，不会直接跳到运行

基本三态模型中没有“就绪 → 阻塞”：就绪任务未占用 CPU 执行指令，不可能自行发起阻塞操作。同样也不画“阻塞 → 运行”直接边：唤醒后逻辑上必须先进入就绪队列，经由调度器裁决后才获得 CPU。

例子：A 正在运行并请求一次需要等待的磁盘读取，于是 A：运行→阻塞；调度器选择 B，于是 B：就绪→运行。磁盘读取完成时，A：阻塞→就绪。此时 B 可以继续运行，直到调度规则决定切换。

1.3 PCB 与上下文：系统记住了什么

信息类型	具体内容	核心用途
身份与关系	PID、PPID、UID/GID、进程组	标识进程身份与权限，维护进程家族树
调度控制	运行状态、动态优先级、已耗 CPU 时间	决定任务能否运行及排队优先级
执行上下文	程序计数器（PC）、栈指针（SP）、通用寄存器、状态字	暂存运行现场快照，恢复后可原地继续执行
内存与资源	页表基址、虚拟内存区域（VMA）、打开文件描述符表	确保恢复执行时面对正确的内存空间与文件资源

什么是上下文？两层上下文保存在哪里？

上下文（Context） 是某一时刻 CPU 所有内部寄存器的状态快照（包括程序计数器 PC、栈指针 SP、通用寄存器及状态标志寄存器 Flags）。物理 CPU 只有一套寄存器，暂停进程前必须把这些值保存下来，以便恢复时原地继续运行。

操作系统中实际上存在两层不同的上下文：

用户态上下文（Trap Frame / 陷阱帧）：存放在当前进程的内核栈顶端。只要发生系统调用、中断或异常（由用户态进入内核态），硬件与中断入口汇编就会将用户态寄存器压入内核栈，用于退出内核时恢复用户现场。
内核态调度上下文（Kernel Context）：存放在该进程的 PCB（或 thread_struct） 中。仅在调度器决定执行进程切换（如调用 switch_to）时，由内核保存当前执行流的内核栈指针与被调用者保存寄存器，用于在不同进程间轮换。

二、进程 API：创建与执行分离

⭐ 考试考点：fork() 函数的具体过程。 重点关注父子进程的返回值、执行位置，以及资源的复制与共享。

以 Unix 风格接口为例：

接口	作用	关键点
`fork()`	创建子进程	成功后父进程获得子 PID，子进程获得 0；失败返回 -1
`exec` 家族	用新程序替换当前进程映像	成功时不返回原调用点，PID 保持不变
`wait()` / `waitpid()`	等待并回收子进程状态	取得退出码并彻底清理子进程 PCB 残留，避免产生僵尸进程
`exit()`	终止当前进程	释放大部分内存资源，退出状态保留在内核等待父进程回收

为什么 Unix 将创建与执行拆分为 fork() 和 exec() 两步？（OSTEP 核心设计哲学）
这种解耦在“子进程创建后”与“执行新程序前”留出了一段宝贵的操作窗口。最典型的受益者是 Shell：
在终端执行 wc -l < input.txt > output.txt 时，Shell 先 fork() 出子进程，在子进程中从容地关闭标准输入输出并重定向到目标文件（通过 open / dup2），随后才调用 exec("wc")。目标程序无需了解任何重定向逻辑，直接向标准输出写入即可，极大提高了系统的模块化与可组合性。

2.1 fork 的具体过程 ⭐

⭐ 考试考点：调用前只有父进程；成功后有父、子两个执行流，都从 fork() 返回处继续。子进程绝不会重新从 main() 开始！

调用 fork() 后，内核为子进程复制一份与父进程近乎完全相同的上下文与执行状态。由于程序计数器（PC）也被复制，子进程不会重新从 main() 执行，而是与父进程一样，从 fork() 系统调用的返回处继续往下跑。

内核通过返回值区分两者的身份：

对子进程：返回 0；
对父进程：返回刚创建的子进程 PID；
发生错误（如系统进程数超限或内存耗尽）：返回 -1，不创建子进程。

从调用者角度，可以把创建过程理解为：

父进程调用 fork()
  → 请求内核创建子进程
  → 建立子进程身份、资源引用与执行上下文（PC 指向 fork 返回点）
  → 准备子进程的地址空间语义（写时复制）
  → 父进程返回子 PID；子进程返回 0
  → 两者分别继续执行后续代码，先后顺序由调度器决定

这是接口行为的概念模型。返回值不是当前进程自己的 PID；当前 PID 用 getpid() 查询。接口语义核对：Linux fork(2)。

2.2 fork 后到底共享什么

父子进程拥有各自独立的虚拟地址空间语义，普通变量后续的修改互不可见。

私有变量与写时复制（COW）：若每次 fork() 都物理复制全部内存，开销极大且通常无意义（子进程往往紧接着调用 exec()）。现代系统采用写时复制（Copy-on-Write）：创建时父子共享物理只读页，仅当某一方尝试写入修改时，硬件触发写保护缺页异常，内核才为此页分配并复制私有物理副本。既保证了逻辑隔离，又兼顾了创建性能。
文件描述符与文件偏移量：父子各自的描述符表是独立的，但继承的表项指向同一个内核打开文件描述（Open File Description）。因此，父子进程共享文件读取/写入偏移量（File Offset）。父进程读取若干字节后，子进程接着读取会从新的偏移量继续。

对象	父子进程之间的关系	机制说明
PID	互不相同	子进程分配独立的进程标识符
普通私有变量	初始值相同，后续修改各自独立	写时复制（COW），按需分配私有物理页
执行位置	均从 `fork()` 返回点继续	寄存器 PC 相同，已停在同一调用返回处
继承的文件描述符（fd）	描述符表各自独立，指向同一内核文件对象	共享文件偏移量指针
显式共享内存映射	完全共享可见	专门申请的公共共享内存，用于 IPC 通信

2.3 一段可运行的 fork 示例

以下示例适用于支持 POSIX 进程接口的环境，并假设调用者是单线程程序。重点观察：执行从哪里继续、x 是否共享，以及 waitpid() 对输出顺序的影响。

#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <unistd.h>

int main(void) {
    int x = 10;
    pid_t pid = fork();

    if (pid < 0) {
        perror("fork");
        return EXIT_FAILURE;
    }
    if (pid == 0) {
        x = 20; // 子进程修改私有副本，不会影响父进程的 x
        printf("child: x=%d\n", x);
        return EXIT_SUCCESS;
    }

    int status;
    // 父进程主动等待子进程收工
    while (waitpid(pid, &status, 0) == -1) {
        if (errno == EINTR) continue;
        perror("waitpid");
        return EXIT_FAILURE;
    }
    printf("parent: x=%d\n", x); // 输出仍为 10
    return WIFEXITED(status) ? WEXITSTATUS(status) : EXIT_FAILURE;
}

保存为 fork_demo.c，编译运行：

cc -std=c11 -Wall -Wextra fork_demo.c -o fork_demo
./fork_demo

正常运行时输出：

child: x=20
parent: x=10

子进程修改的是自己的 x。父进程的输出位于等待之后，所以本例中子进程先完成输出；这不是 fork() 自动保证子进程先运行。去掉等待关系后，就不能依赖这样的顺序。

2.4 输出顺序与缓冲的两个问题

fork() 成功后，父子进程谁先运行通常没有保证。若 fork() 之前有尚未刷出的标准 I/O 缓冲，缓冲内容会被一同复制到子进程中；后续双方退出刷新时可能出现重复输出。关键在于复制了未刷新的用户态缓冲区，并非子进程回头重新执行了前面的 printf()。分析题目时，可在 fork() 前调用 fflush() 排除干扰。

进程数量题也要沿控制流计算：连续执行 $n$ 次无条件 fork()，只有在每个现存进程都执行每一次调用、调用全部成功且中途不退出时，总数才为 $2^n$ ，新增数为 $2^n-1$ 。遇到分支、短路运算和 exec() 时，应画进程树逐条判断。

2.5 exec、wait 与退出：把生命周期接起来

exec()：成功后替换原程序映像，建立新程序所需的地址空间并转到新入口，PID 保持不变。这里的“替换”不要求逐字节物理覆盖原内存，也不要求一次性把新程序全部读入内存。Linux execve(2)。
僵尸进程（Zombie）：子进程已终止退出，内核已释放其大部分内存资源，但仍保留其 PID、退出状态及 CPU 用时统计等元数据，等待父进程调用 wait() / waitpid() 读取并释放。若父进程迟迟不回收，僵尸进程将持续占用系统的 PID 资源。
孤儿进程（Orphan）：原父进程先退出，存活的子进程成为孤儿。在 Linux 上它会被最近的子收割者（subreaper）或 1 号进程（init / systemd）接管。接管者会在其退出时负责回收。

教材 §4.5（书内第 25 页）把僵尸作为“已退出但尚未清理”的最终状态介绍：保留这段状态，是为了让父进程知道子进程是否成功完成。

对比	僵尸进程	孤儿进程
关键条件	自己已经退出，尚未被回收	原父进程先退出
是否还能执行	不能，已终止	可以，仍可能运行、就绪或阻塞
系统如何处理	等待父进程或接管者读取退出状态并回收	重新指定父进程，退出后仍需按规则回收
记忆点	子已退出，记录未收	父先退出，关系改挂

孤儿不是三态模型之外的一种调度状态。 它描述的是父子关系；僵尸描述的是退出后的生命周期阶段。二者不应与“运行、就绪、阻塞”并排当成同一分类。

短暂的僵尸阶段通常是正常现象，长期大量积累才说明回收机制有问题。对僵尸发送 kill -9 不能代替回收：它已经没有可终止的执行流，需要处理的是父进程的回收逻辑。显式设置 SIGCHLD 为 SIG_IGN 或使用 SA_NOCLDWAIT 等配置还可改变退出状态的保留行为，因此“子进程退出后一定留下僵尸”也不准确。Linux wait(2)。

Shell (父进程)
   ↓ fork()
子进程 (克隆 Shell 镜像) ──[黄金操作空窗期：可随意重定向 fd 0/1/2]
   ↓ exec("外部命令")
新程序接管 (代码与内存彻底替换，PID 不变)
   ↓ 执行完毕 exit(0)
僵尸状态 (只剩墓碑和退出状态)
   ↓
Shell 调用 waitpid() ──[收殓尸体，销毁墓碑]──> 资源彻底清空

实际 Shell 对内建命令、管道和后台任务另有处理；上述过程用于说明一个外部命令的基本生命周期。

2.6 与计算机系统课程串起来：退出、信号与回收

之前的《计算机系统 - 程序执行》第七节已经讲过：fork → execve → 动态链接 → _start → main → exit → waitpid。操作系统这里补上的重点是最后两步：程序停止执行，与内核清理其退出记录，是两件事。

在《CSAPP - Shell Lab》的 waitfg && sigchld_handler 部分，之前遇到过：子进程结束了，Shell 却一直认为前台任务还在。这里需要区分三层工作：

SIGCHLD 是通知：告诉 Shell 子进程发生了状态变化；收到信号本身不等于已完成回收，而且通知也可能对应停止等事件。
waitpid() 读取状态：对已经终止的子进程完成回收；若报告的是停止状态，该进程还活着，不能当成退出处理。
deletejob() 更新 Shell 自己的任务表：这张用户态表不是内核进程表。只删任务记录不能回收僵尸；只回收却不更新任务表，也可能让 waitfg 继续误判。

Shell Lab 用 while (waitpid(-1, &status, WNOHANG | WUNTRACED) > 0) 循环处理可取得的子进程状态，因为普通 SIGCHLD 信号可能合并，一次通知不一定只对应一个子进程事件。WNOHANG 让当前没有可报告状态时立即返回，避免处理函数一直等；具体终止、停止等情况再通过 WIFEXITED、WIFSIGNALED、WIFSTOPPED 分别判断。

关联自测：后台命令结束后，Shell 还能接收输入，是否说明没有僵尸？——不能。交互正常和回收正确是两回事；后台任务也需要回收，只是不必让主交互流程一直阻塞等待它。

2.7 在 Linux 里观察这些概念

学到进程时，可以直接用下面的命令观察，不必先写实验程序：

# 查看进程身份、父进程、状态和命令行
ps -eo pid,ppid,stat,comm,args

# 当前 Shell 的 PID 是 $$；观察它由谁启动
echo $$
ps -p "$$" -o pid,ppid,stat,args

# 查看进程树及 PID（需安装提供 pstree 的 psmisc 工具包）
pstree -p

# 动态观察 CPU 使用情况
top

PID 是进程号，PPID 是当前父进程号。STAT 的第一个字母表示主要状态，后面的字符提供附加信息，例如 + 表示属于终端的前台进程组。

Linux 常见状态	含义	与本章的联系
`R`	正在运行，或处于可运行队列	不区分教材中的“运行”和“就绪”
`S`	可中断睡眠，等待事件	常见的等待状态，例如等待输入或计时结束
`D`	不可中断睡眠，常见于某些 I/O 等待	不能简单理解为“程序死了”，也不保证发信号就立即退出
`T`	被作业控制信号停止	如 `Ctrl-Z`，不是已经退出；可继续执行
`Z`	僵尸，已退出但尚未回收	对应前面的退出记录保留阶段

Linux 的状态码比教材三态模型更细。 特别是 R 同时包含运行与就绪；孤儿进程没有专门的“孤儿状态字母”，需要结合父子关系变化判断，单看 PPID=1 也不能还原它的全部生命周期。

在交互式 Shell 中，jobs -l 查看的是当前 Shell 管理的作业，ps 查看的是系统进程；一个管道作业还可能包含多个进程。Ctrl-Z 停止前台作业，bg 让停止的作业在后台继续，fg 将作业带回前台——这正好对应 Shell Lab 中的 SIGTSTP、SIGCONT 和前后台任务管理。

另一个易混点：Shell 的 wait 是内建命令，用来等待它管理的子进程或作业；C 程序中的 wait() / waitpid() 是进程等待接口。它们有关联，但不是同一个使用层次，Shell 也不能靠 wait 任意回收其他进程的子进程。

观察题：sleep 通常显示 S 而不是 Z，为什么？——它仍活着，只是在等待计时完成；僵尸则已经结束执行，只剩待回收记录。

2.8 本机实录：亲眼看到父子进程与等待状态

下面的输出采集于 2026-09-20 的 macOS／Darwin arm64 环境，是实际运行结果。它同属 Unix 环境，但工具参数、调度实现和部分状态显示与 Linux 不完全相同；不要把 macOS 输出当成 Linux 截图。

用一个四秒后自动结束的 sleep，观察父子关系：

/bin/zsh -f -c 'sleep 4 & demo_pid=$!; ps -p $$,$demo_pid -o pid,ppid,stat,ni,comm; wait $demo_pid'

实际输出：

  PID  PPID STAT NI COMM
94990 80124 Ss    0 /bin/zsh
94991 94990 SN    5 sleep

看关系：sleep 的 PID 是 94991，PPID 是 94990，正好对应上面那一行 Shell 的 PID。这就是父子关系在进程表中的表现；PID 每次运行都可能不同。
看状态：两行的首字母都是 S，表示采样时处于睡眠。sleep 在等待时间到达，Shell 此时也在等待前台的 ps 命令完成；输出结束后才执行后面的 wait，等待后台 sleep 结束。
看附加标记：按本机 man ps，小写 s 表示会话首进程，N 表示降低了 CPU 调度优先级。它们不是另外两种独立的主状态。
看 NI：本次 Shell 为 0，后台 sleep 为 5。这与 zsh 默认开启的 BG_NICE 行为相符：后台作业以较低优先级运行。不能因此推出“所有 Shell 中加 & 都必然让 NI 变成 5”。本机 man zshoptions 可查该选项。

$$ 是当前 Shell 的 PID，$! 是最近一个后台任务的 PID，& 表示让命令在后台执行。最后的 wait 使 Shell 等待并取得这个子进程的结束状态，整个例子会自行结束。

2.9 本机 top：为什么 sleeping 也有 CPU 使用率

macOS 的 top 可以用日志模式采样两次，间隔一秒，并只显示指定字段：

top -l 2 -s 1 -n 5 -o cpu -stats pid,command,cpu,mem,threads,state

下面节选第二次采样的概况和两行进程数据，其余输出省略。选择第二次，是因为本机 man top 明确说明，首次采样的进程 %CPU 缺少前一次采样作为有效计算基准。

Processes: 704 total, 4 running, 700 sleeping, 5423 threads
Load Avg: 8.03, 4.66, 4.22
CPU usage: 23.45% user, 12.47% sys, 64.7% idle

PID    COMMAND          %CPU MEM    #TH    STATE
608    WindowServer     42.8 1224M- 24     sleeping
0      kernel_task      19.6 67M-   714/10 running

先看整机：这次采样中，进程总数为 704，线程总数为 5423，二者不是同一个数量；CPU 概况把时间分为用户态、内核态和空闲部分。

再看单个进程：WindowServer 的状态是 sleeping，但 %CPU 为 42.8，并不矛盾。状态表示采样时观察到的状态，CPU 使用率反映前后两次采样之间消耗的 CPU 时间；它完全可能先运行了一段时间，再进入等待。多线程进程的汇总信息还涉及多个线程，不能把它简单当成一条永不变动的状态线。

本机的 MEM 表示进程的物理内存占用指标（physical memory footprint），不是 Linux VIRT，也不能不加区分地当成 Linux RES。末尾的 - 表示相较上次采样减少，+ 则表示增加。#TH 是线程数，斜线后若显示数字，则是运行中的线程数：这里 714/10 表示总计 714 个线程，其中 10 个被报告为运行中。

2.10 Linux top 字段速查：PID、PR、NI 到底是什么

Linux 上常见的是 procps-ng 的 top，典型表头如下。这里只列字段，未将本机 macOS 数据伪装为 Linux 输出。 字段顺序、单位及可见列都可以配置。

PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND

字段	含义	阅读时关注什么
`PID`	进程标识	用于定位任务；线程模式下需区分线程 ID
`USER`	有效用户名	任务当前以谁的身份运行
`PR`	优先级显示	用于理解调度，详见下文
`NI`	nice 值	普通任务的调度权重调节参数
`VIRT`	虚拟内存总量	包含映射、预留等，不等于实际占用 RAM
`RES`	驻留物理内存	当前驻留、未换出的部分
`SHR`	可共享驻留内存部分	不代表这些页此刻一定被多个进程同时使用
`S`	进程状态	如 `R`、`S`、`D`、`T`、`Z`
`%CPU`	采样区间 CPU 使用率	多线程任务在按单个逻辑 CPU 为 100% 的显示模式下可超过 100%
`%MEM`	驻留内存占物理内存的比例	通常对应 RES，而非 VIRT
`TIME+`	累计 CPU 时间	精确显示到百分之一秒，不是启动后经过的墙上时间
`COMMAND`	程序名或命令行	可切换显示方式

常用交互键：P 按 CPU 排序，M 按内存排序，1 切换各逻辑 CPU 的显示，H 切换线程视图，q 退出。字段与按键参考：procps-ng top(1)。

PR 与 NI：优先级和“谦让程度”

对 Linux 常规 nice 调节机制而言，NI 越小，通常获得越高的调度权重：-20 最不谦让，19 最谦让，0 是常见默认值。它影响有竞争时的 CPU 分配，不是固定百分比配额，也不是“每次必须先运行”的保证；睡眠或等待 I/O 的任务不会因为 NI 更小就立即获得所需事件。Linux nice(2)。

普通非实时任务常见的 top 显示关系是 PR = 20 + NI：

NI	常见 PR	直观理解
-5	15	相对更积极地竞争 CPU
0	20	默认基准
5	25	相对更谦让

这里的数字越小通常表示优先级越高。不要将此关系套到实时任务或 macOS 的优先级字段上。 Linux 实时调度有独立的优先级与策略，top 可能显示 rt 等形式；调度策略、CPU 亲和性和资源分组等条件也会影响实际运行结果。内核导出的 priority／nice 定义。

顶部概况：负载不等于 CPU 百分比

Linux 的 load average 三个值对应最近 1、5、15 分钟的平均负载，统计可运行任务以及不可中断等待任务。它不是百分数，也不只是“有多少进程正在 CPU 上执行”；判断是否拥挤需要结合可用逻辑 CPU 数和等待原因。例如负载较高、CPU 却不忙，可能与不可中断 I/O 等待有关，不能只凭一个数字下结论。Linux uptime(1)。

读资源表时，可以沿着三条线思考：PR／NI 联系调度策略，S 联系状态转换，VIRT／RES 联系虚拟内存。同一个 top 界面其实把后面几章的知识放到了一起。

三、受限直接执行（Limited Direct Execution）与上下文切换

CPU 虚拟化面临着操作系统的核心挑战：如何在让程序获得原生执行性能的同时，保持操作系统的安全性与绝对控制权？

3.1 什么是受限直接执行（LDE）？

若由操作系统逐条解释模拟用户指令，安全性虽高但性能极低（开销可达数十倍）；若直接将程序置于裸机硬件上全速运行，操作系统又无法防范死循环或破坏性操作。

受限直接执行（LDE） 的折中方案是：

常规指令直接在物理 CPU 上全速执行（直接执行）；一旦涉及硬件资源或潜在破坏性操作，必须受控由内核接管，且死循环可被硬件强行打断（受限）。

维度	“直接执行”（Direct Execution）	“有限 / 受限”（Limited）
核心目的	获得硬件原生性能，消除软件模拟开销	守住安全底线，实现进程隔离与分时共享
执行模式	普通算术、逻辑指令直接由物理 CPU 运算	运行在用户态，硬件级禁止直接访问外设与敏感寄存器
特权操作	—	通过 Trap 指令（系统调用）受控进入内核态代办
防死循环	—	依赖硬件时钟中断（Timer Interrupt）周期性强制夺回控制权

3.2 限制一：阻止越权——用户态与内核态的关系

用户态与内核态的划分并非两个独立进程，而是 CPU 硬件层面的特权级分离（如 x86 的 Ring 3 与 Ring 0，ARM 的 EL0 与 EL1）：

指令分级：
- 特权指令：只能在内核态执行。包括开关硬件中断（cli/sti）、直接读写 I/O 端口、修改页表基址寄存器（如 CR3）、停机（hlt）等。用户态尝试执行会触发硬件异常，由内核终止该进程。
- 非特权指令：用户态和内核态皆可执行。包括通用寄存器算术运算、用户栈操作、函数跳转等，完全由硬件直接执行。
跨越边界的三道闸门与中断向量表（IVT）：
用户程序无法自行提升特权级，只能通过以下硬件机制进入内核态：
- 系统调用（Trap）：同步触发。程序主动请求内核服务（如 read()、fork()）。
- 异常 / 故障（Fault）：同步触发。当前指令发生错误（如除以零、段错误、缺页异常）。
- 硬件外部中断（Interrupt）：异步触发。外设引脚发出的电信号（如时钟中断、网络包到达）。
中断向量表与上下文保存的软硬件协同：
中断向量表（Interrupt Vector Table, IVT / 陷阱表 Trap Table） 是开机时内核初始化的一张函数指针数组，负责将中断/异常向量号映射到对应内核处理程序的起始地址（解决“出了事跳去哪里”）。
当中断或 Trap 发生时，CPU 绝不能直接跳转，否则会瞬间冲刷覆盖用户正在使用的寄存器。两者的协同保存流程如下：
- 查表与硬件自动压栈：CPU 根据向量号查中断向量表获取入口地址；同时，硬件自动切换至该进程的内核栈，并在跳转前自动将核心寄存器（PC、SP、Flags、CS 等）压入内核栈；
- 软件压栈构建 Trap Frame：跳转到中断向量表指向的处理程序入口后，第一段汇编代码将剩余的通用寄存器（RAX、RBX 等）全部压入内核栈，形成完整的用户态上下文（Trap Frame / pt_regs）；
- 内核处理与恢复现场：内核完成业务逻辑后，汇编弹出通用寄存器，最后执行 iret / return-from-trap 指令，硬件自动从内核栈弹回核心寄存器并降权切回用户态，原程序无缝继续。
- 关系本质：中断向量表负责路由寻址（跳去哪），而内核栈上的上下文压栈负责保护现场（怎么恢复）。两者在硬件流水线与处理入口处严密咬合。
为什么必须使用双栈模型（用户栈 vs 内核栈）？
每个进程都配有一个私有的用户栈和一个小型的内核栈（通常 8KB/16KB）：
- 安全性：用户栈位于用户空间，用户指针可随意读写。若特权级现场和内核函数调用帧压入用户栈，恶意代码可篡改返回地址直接劫持内核；
- 健壮性：用户栈可能发生溢出或指针损坏。进入内核时切换到预设的专用内核栈，可避免在压栈保护现场时引发连续故障导致整机崩溃。
虚拟地址空间与故障隔离：
内核空间通常常驻于每个进程虚拟地址空间的高位（通过页表项 U/S 标志位进行硬件阻隔）。因此，系统调用发生时仅改变 CPU 特权模式，无需切换页表基址（CR3），也无需刷新 TLB 缓存。
- 故障隔离：用户态程序崩溃仅导致该进程被终止（如抛出 SIGSEGV）；内核态代码若发生崩溃则意味着系统核心失控，只能触发 Kernel Panic 或蓝屏停机。

3.3 限制二：防止独占——时钟中断夺回控制权

若程序陷入 while(1); 死循环且不发起任何系统调用，早期协作式系统（依赖主动 yield() 让出 CPU）将彻底瘫痪。

现代系统采用非协作式的硬件时钟中断（Timer Interrupt）：

开机时内核启动硬件时钟芯片，每隔数毫秒至数十毫秒触发一次中断信号；
硬件强行暂停当前用户程序，保存现场至内核栈，并将 PC 跳转到内核的时钟中断处理程序；
操作系统由此重新掌握 CPU，调度器可从容决定是否切换到下一个进程。

3.4 模式切换 vs 进程切换（概念辨析）

切换类型	触发场景	地址空间是否切换	主要开销	说明
模式切换（Mode Switch）	系统调用或中断进入内核，处理完返回原进程	不改变	保存/恢复少量寄存器至内核栈，开销极小	同一进程在用户态与内核态之间切换
进程切换（Process Switch）	调度器决定挂起当前进程，改运行另一进程	必须切换	切换页表基址、导致 TLB 及 CPU 缓存大面积失效、保存/恢复完整 PCB	代价远高于模式切换

四、先定义调度指标

调度算法的核心在于权衡。令到达时间为 $A_i$ ，首次执行时间为 $S_i$ ，完成时间为 $C_i$ ：

T_{\text{turnaround},i} = C_i - A_i, \qquad T_{\text{response},i} = S_i - A_i

周转时间（Turnaround Time）：任务从到达至彻底完成的总耗时，侧重于批处理任务的整体吞吐。
响应时间（Response Time）：任务从到达至首次获得 CPU 服务的时间，侧重于交互式任务的流畅度。

在无 I/O 阻塞的简单场景下， $\text{等待时间} = \text{周转时间} - \text{CPU执行时间}$ 。

五、基本调度算法

算法	调度策略	核心优点	主要局限
FIFO / FCFS	先来先服务，运行至完成或阻塞	逻辑最简单，调度开销最小	护航效应（Convoy Effect）：长任务排在队首阻碍短任务，拖垮整体周转时间
SJF	最短作业优先（非抢占）	全员同时到达时，平均周转时间最优	需预知执行时间；长任务可能饥饿
STCF / SRTF	最短剩余时间优先（抢占式）	短任务到来时立即抢占，进一步优化周转	仍需剩余时间信息，长任务饥饿依然存在
RR	时间片轮转，就绪队列轮流执行	首次响应时间极佳，交互极其流畅	对长任务的平均周转时间较差；时间片过短则上下文切换开销占比过高

5.1 手算示例

假设 A、B、C 都在时刻 0 同时到达，CPU 时间分别为 8、4、1，无 I/O、切换开销忽略不计，初始就绪顺序为 A→B→C。

调度策略	执行时序	完成时刻 $(C_A, C_B, C_C)$	平均周转时间	首次响应时刻 $(S_A, S_B, S_C)$	平均响应时间
FIFO	`A(8) -> B(4) -> C(1)`	$8, 12, 13$	$(8+12+13)/3 = \mathbf{11}$	$0, 8, 12$	$(0+8+12)/3 = \mathbf{6.67}$
SJF	`C(1) -> B(4) -> A(8)`	$13, 5, 1$	$(13+5+1)/3 = \mathbf{6.33}$	$5, 1, 0$	$(5+1+0)/3 = \mathbf{2}$
RR ( $Q=1$ )	`A(1)->B(1)->C(1)->A(1)->B(1)...`	$13, 10, 3$	$(13+10+3)/3 = \mathbf{8.67}$	$0, 1, 2$	$(0+1+2)/3 = \mathbf{1}$

调度的核心矛盾：SJF 在周转时间上表现极佳（6.33），但依赖对运行时间的预先认知；RR 在响应时间上极佳（1），但拉长了任务的整体完成时间。现实中操作系统无法预知任务未来的具体执行时长，这催生了自适应的 MLFQ 算法。

六、MLFQ：不知道任务长度怎么办

多级反馈队列（Multi-Level Feedback Queue, MLFQ） 的目标是在无法预知任务执行时间的前提下，兼顾短任务的低周转时间与交互式任务的高响应性。

核心思想是基于历史行为动态调整优先级：

优先级分层：系统维护多级就绪队列，高优先级队列优先调度；同级任务采用 RR。
初始乐观假设：新任务默认进入最高优先级队列（假设其为交互型短任务），使其立即获得极短的响应时间。
CPU 密集型降级：若任务在当前优先级累计耗尽了 CPU 配额（Time Allotment），说明其为长计算任务，调度器将其降入下一级低优先级队列。越底层的队列分配的时间片通常越长，以减少切换开销。
配额累计记账（防作弊）：记录任务在当前层级消耗的 CPU 累计物理时间。即使任务在时间片末尾主动让出 CPU（如做微小 I/O），配额也不重置，用满即降级，防止恶意霸占高优先级。
优先级周期性提升（Priority Boost）：每隔固定时间周期 $S$ ，将系统中所有任务全部重置回最高优先级队列。此举一方面避免底层长任务因高层不断有新任务涌入而饥饿，另一方面让行为突变为交互型的任务重新回到高层。

[顶层 Q2] (时间片小, 响应极快) ──新任务进入──> 执行完毕退出
    │ (用完本级配额后降级)
    ↓
[中层 Q1] (时间片适中) ──────────────────────> 执行完毕退出
    │ (用完本级配额后降级)
    ↓
[底层 Q0] (时间片大, 适合批处理长计算) ──────> 执行完毕退出
    ▲
    └──────── 每隔固定周期 S: 全部提升回最高优先级 (Priority Boost) ────────┘

七、比例份额与多处理器

7.1 彩票调度 vs 步长调度

除了指标优化，另一类算法关注**比例份额（Proportional Share）**调度，即按权重保证 CPU 份额：

彩票调度（Lottery Scheduling，概率型）：任务按权重持有彩票，每轮随机摇号选中者运行。实现极度轻量且无状态，动态增删任务只需增减彩票；但短期内受随机波动影响，份额不绝对精确。
步长调度（Stride Scheduling，确定型）：步长 $S$ 与票数成反比（ $S = L / \text{票数}$ ）。每次选择累计行程 pass 最小者运行并累加步长（pass += S）。在任何时间区间内份额均精确按比例分配；但新加入任务时其初始 pass 值的设定较为复杂。

7.2 多处理器调度：缓存亲和性 vs 负载均衡

现代多核系统中，调度器需权衡 缓存亲和性（Cache Affinity） 与 负载均衡（Load Balancing）：

单队列调度（SQMS）：所有核共享一个全局就绪队列。负载天然均衡，但核间对全局队列锁争用严重，且任务在不同核之间漂移会导致 CPU 缓存命中率严重下降。
多队列调度（MQMS）：每个核心维护独立的专属就绪队列。各核无锁争用，任务固定在同一核上执行故缓存利用率极高；但容易出现某些核空闲而某些核过载的负载不均现象。
工作窃取（Work Stealing）：MQMS 的通用解决方案——空闲核心主动从负载过高的其他核队列尾部“窃取”任务执行，兼顾了局部缓存亲和与全局负载均衡。

八、自测与核心记忆点

⭐ 启动程序成为进程需要哪些步骤？
- 建记录 → 建空间 → 备环境 → 设上下文 → 等调度。分配 PCB、建立虚拟地址空间、初始化栈空间与参数、设定 PC/SP 等初始上下文，放入就绪队列等待调度器选中。
⭐ I/O 完成后，状态为什么是“阻塞 → 就绪”而不是直接“阻塞 → 运行”？
- I/O 完成仅代表任务重新具备了运行条件，必须重新进入就绪队列接受调度器的裁决与 CPU 分配，逻辑上不能直接抢占正在运行的进程。
⭐ fork() 后子进程从哪里开始执行？为什么不从 main() 开始？
- 从 fork() 返回点继续向下执行。因为子进程复制了父进程当时的执行上下文（包括程序计数器 PC）；内核通过返回值区分身份（子进程返回 0，父进程返回子 PID）。
Unix 为什么把进程创建拆分为 fork() 与 exec() 两部分？
- 为子进程在创建后、运行新程序前留出了环境配置的操作窗口（如重定向标准 I/O、建立管道），目标程序无需包含任何外部重定向代码。
为什么子进程修改局部变量（如 x = 20）不会影响父进程？
- 父子拥有各自独立的虚拟内存空间。物理上采用写时复制（COW）：未写入时共享只读页，一旦写入触发写保护异常，内核按需为修改方分配私有物理页。
阻塞进程应不应该继续占用 CPU？为什么没有“就绪 → 阻塞”？
- 不应占用，空等浪费算力；就绪任务未占用 CPU 执行指令，不可能自行发起阻塞操作。
SJF 在现实通用系统中能否直接使用？
- 不能。因为现实中操作系统无法预先知道任务的具体执行时间；现代通用系统采用 MLFQ（多级反馈队列），通过历史运行行为动态反馈并调整优先级。
exec() 是否创建了新进程？僵尸进程与孤儿进程的区别是什么？
- exec() 不创建新进程，只是替换当前进程的程序映像，PID 保持不变；
- 僵尸进程：已终止但退出状态尚未被父进程 wait() 回收，内核仍保留其 PCB 记录；
- 孤儿进程：原父进程先退出，存活的子进程被系统祖先（如 init / systemd）接管关系。
什么叫做受限直接执行（Limited Direct Execution, LDE）？
- “直接执行”让非特权指令直接在物理硬件上运行以追求原生性能；“受限”通过特权级分离（用户态/内核态）限制硬件访问，并通过硬件时钟中断防止死循环霸占 CPU，从而在高性能与强控制之间取得平衡。
用户态与内核态的核心区别是什么？为什么发生系统调用进入内核时必须切换到内核栈？
- 区别：硬件模式位赋予的权限不同。用户态仅能执行非特权指令且内存访问受限；内核态拥有对所有硬件外设与特权指令的最高控制权。
- 切换内核栈的原因：
  1. 安全性：用户栈位于用户空间可被指针任意篡改，内核栈受保护，防止恶意代码劫持特权执行流；
  2. 健壮性：用户栈可能已溢出或指针非法，使用独立的内核栈可避免内核压栈时引发连续硬件故障导致整机崩溃。
中断向量表（IVT）与上下文保存是什么关系？两层上下文分别保存在哪里？
- 关系：中断向量表负责“寻址路由”（依据中断/陷阱向量号告诉 CPU 该跳往哪个内核处理入口），上下文压栈负责“保护现场”（在打断当前指令流前将寄存器快照保存下来，以便后续恢复）；两者在硬件进入内核态时紧密咬合。
- 保存位置：
  1. 用户态上下文（Trap Frame / 陷阱帧）：保存在当前进程的内核栈顶端（硬件自动压入 PC/SP/Flags + 汇编压入通用寄存器）；
  2. 内核态调度上下文：保存在进程的 PCB（或 thread_struct） 中（由调度器 switch_to 在进程切换轮转时保存与恢复）。

教材主题可从 OSTEP 作者目录查阅第 4—10 章；API 的具体语义可结合本篇链接的系统手册核对。